package 算法.leetcode.sort;

import com.alibaba.fastjson.JSON;

/**
 * @author liclong
 * @create 2020-09-22 16:24
 * @desc 选择排序
 **/
public class SelectionSort {
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 7, 4, 9, 6};
        selectionSort(array, array.length);
        System.out.println(JSON.toJSONString(array));
    }

    /**
     * 选择排序【不稳定】【原地】【O(n2)】
     *
     * @param array 待排序数组
     * @param n 数组大小
     */
    public static void selectionSort(int[] array, int n) {
        if (n <= 1) {
            return;
        }

        // [0,i]未已排序区间
        for (int i = 0; i < n - 1; i++) {
            int value = array[i];
            for (int j = i + 1; j < n; j++) {
                // 取未排序区间的数据与排序区间最后一个比较,选择未排序区间最小的一个数据与已排序区间的最大数据交换
                if (array[j] < value) {
                    Base.swap(array, j, i);
                }
            }
        }
    }
}
